package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * https://leetcode.com/problems/maximal-square/
 * see LC85
 *
 * @author tzp
 * @since 2020/9/24
 */
public class LC221 implements DynamicProblem {
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int max = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != '1') {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        int leftUp = dp[i - 1][j - 1];
                        int left = dp[i][j - 1];
                        int up = dp[i - 1][j];
                        dp[i][j] = 1 + Math.min(leftUp, Math.min(left, up));
                    }
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }

    public static void main(String[] args) {
//        char[][] a = {
//                {'1', '0', '1', '0', '0'},
//                {'1', '0', '1', '1', '1'},
//                {'1', '1', '1', '1', '1'},
//                {'1', '0', '0', '1', '0'}};
//        char[][] a = {};
//        char[][] a = {{}};
//        char[][] a = {{'0'}};
//        char[][] a = {{'1'}};
        char[][] a = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}};

        System.out.println(new LC221().maximalSquare(a));
    }
}
